// Copyright 2022 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "components/user_notes/browser/user_note_utils.h"

#include <algorithm>
#include <memory>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#include "base/test/scoped_feature_list.h"
#include "base/time/time.h"
#include "base/unguessable_token.h"
#include "components/user_notes/browser/frame_user_note_changes.h"
#include "components/user_notes/browser/user_note_manager.h"
#include "components/user_notes/interfaces/user_note_metadata_snapshot.h"
#include "components/user_notes/model/user_note_model_test_utils.h"
#include "components/user_notes/user_notes_features.h"
#include "content/public/browser/page.h"
#include "content/public/browser/render_frame_host.h"
#include "content/public/browser/web_contents.h"
#include "content/public/test/navigation_simulator.h"
#include "content/public/test/test_renderer_host.h"
#include "testing/gtest/include/gtest/gtest.h"
#include "url/gurl.h"

namespace user_notes {

namespace {

using NoteIdList = std::vector<int>;

const char kUrl1[] = "https://www.google.com/1";
const char kUrl2[] = "https://www.google.com/2";
const char kUrl3[] = "https://www.google.com/3";
const char kUrl4[] = "https://www.google.com/4";
const char kUrl5[] = "https://www.google.com/5";

const base::Time kInitialTimeStamp = base::Time::FromDoubleT(1000);
const base::Time kUpdatedTimeStamp = base::Time::FromDoubleT(2000);

// An enum describing the different types of update that can happen to a note
// during a test case. This determines what kind of updated metadata will be
// generated during the test.
enum NoteUpdateType {
  // The updated metadata will be the same as the note's initial metadata.
  UNCHANGED = 0,

  // The note will not be added to frames at test setup time, but the update
  // snapshot will have a metadata entry for it.
  ADDED,

  // The updated metadata will have a later modification timestamp than the
  // note's initial metadata.
  MODIFIED,

  // No metadata will be generated for this note in the update snapshot.
  REMOVED
};

// Configuration for simulating a note in a test case.
struct NoteConfig {
  NoteConfig(int id,
             std::string url,
             NoteUpdateType update = NoteUpdateType::UNCHANGED)
      : test_id(id), target_url(url), update_type(update) {}

  // A test-only, stable ID to use for this note, which makes test case
  // authoring simpler and test output easier to understand compared to using
  // `base::UnguessableToken` directly. An actual `base::UnguessableToken` will
  // be generated by the test setup for building this note. The token will be
  // mapped to this test ID to ensure consistency.
  int test_id;

  // The URL for this note's target page.
  std::string target_url;

  // Configures what kind of updated metadata should be generated during the
  // test for this note. If set to `ADDED`, the test setup will not add this
  // note to any frame. For every other update type, a note instance will be
  // added at test setup time to each frame whose URL corresponds to this note's
  // target URL. Defaults to `UNCHANGED`.
  NoteUpdateType update_type;
};

// Configuration for initializing one `RenderFrameHost` during a test case and
// setting its diff expectations.
struct FrameConfig {
  explicit FrameConfig(int id, std::string url) : test_id(id), url(url) {}

  bool operator==(const FrameConfig& other) const {
    return other.test_id == test_id;
  }

  // Sets the expectations for the added notes.
  FrameConfig& ExpectAdded(const NoteIdList& notes) {
    expect_diff = true;
    added = notes;
    return *this;
  }

  // Sets the expectations for the modified notes.
  FrameConfig& ExpectModified(const NoteIdList& notes) {
    expect_diff = true;
    modified = notes;
    return *this;
  }

  // Sets the expectations for the removed notes.
  FrameConfig& ExpectRemoved(const NoteIdList& notes) {
    expect_diff = true;
    removed = notes;
    return *this;
  }

  // A test-only, stable ID for this frame to help read the test output in case
  // of failures.
  int test_id;

  // The desired URL for this frame. The test setup will navigate this frame to
  // this URL and add to it all notes whose target page corresponds to this URL
  // (except for notes that have an update type of `ADDED`).
  std::string url;

  // Whether a diff is expected to be generated for this frame. Defaults to
  // false.
  bool expect_diff{false};

  // IDs of the notes that the diff should identify as having been added. Order
  // doesn't matter. These IDs must all correspond to one of the IDs used in the
  // `NoteConfig` objects for this test case. Defaults to the empty vector.
  NoteIdList added;

  // IDs of the notes that the diff should identify as having been modified.
  // Order doesn't matter. These IDs must all correspond to one of the IDs used
  // in the `NoteConfig` objects for this test case. Defaults to the empty
  // vector.
  NoteIdList modified;

  // IDs of the notes that the diff should identify as having been removed.
  // Order doesn't matter. These IDs must all correspond to one of the IDs used
  // in the `NoteConfig` objects for this test case. Defaults to the empty
  // vector.
  NoteIdList removed;
};

// A test case for the diff calculation tests.
struct UserNoteDiffTestCase {
  explicit UserNoteDiffTestCase(const std::string& test_name)
      : test_name(test_name) {}

  // Adds a note config to this test case.
  UserNoteDiffTestCase AddNote(const NoteConfig& note) {
    notes.emplace_back(note);
    return *this;
  }

  // Adds a frame config to this test case.
  UserNoteDiffTestCase AddFrame(const FrameConfig& frame) {
    frames.emplace_back(frame);
    return *this;
  }

  // A short description of this test case, that will be used as the generated
  // test name instead of /0, /1, etc.
  std::string test_name;

  // The configuration for the notes in this test case.
  std::vector<NoteConfig> notes;

  // The configuration for the frames in this test case. For each entry, a test
  // frame will be created, navigated to the specified URL, and filled with note
  // instances based on the `notes` configuration.
  std::vector<FrameConfig> frames;
};

// Hasher for using frame configs as keys in an unordered map.
struct FrameConfigHash {
  size_t operator()(const FrameConfig& frame_config) const {
    return std::hash<int>()(frame_config.test_id);
  }
};

// Helper for setting the test case's name.
static std::string DescribeParams(
    const testing::TestParamInfo<UserNoteDiffTestCase>& info) {
  return info.param.test_name;
}

// Helper to copy a vector of test IDs and sort them.
NoteIdList CopyAndSort(NoteIdList test_ids) {
  NoteIdList copy(test_ids);
  std::sort(copy.begin(), copy.end());
  return copy;
}

// Helper method to convert note token IDs to their equivalent test IDs as
// configured in the provided map.
NoteIdList ConvertToSortedTestIds(
    const std::vector<base::UnguessableToken>& token_ids,
    const std::unordered_map<base::UnguessableToken,
                             int,
                             base::UnguessableTokenHash>& token_to_test_id) {
  NoteIdList converted;
  for (const base::UnguessableToken& token : token_ids) {
    converted.emplace_back(token_to_test_id.find(token)->second);
  }
  std::sort(converted.begin(), converted.end());
  return converted;
}

}  // namespace

class UserNoteUtilsTest
    : public content::RenderViewHostTestHarness,
      public testing::WithParamInterface<UserNoteDiffTestCase> {
 public:
  UserNoteUtilsTest() {
    scoped_feature_list_.InitAndEnableFeature(user_notes::kUserNotes);
  }

 protected:
  void SetUp() override {
    content::RenderViewHostTestHarness::SetUp();

    // Create the note service and the note models that will be used in this
    // test case. A service delegate and storage aren't needed for these tests.
    note_service_ = std::make_unique<UserNoteService>(/*delegate=*/nullptr,
                                                      /*storage=*/nullptr);
    for (const NoteConfig& note : GetParam().notes) {
      CreateNewNoteAndAddToService(note);
    }

    // Set up the frames.
    for (const FrameConfig& frame : GetParam().frames) {
      ConfigureNewFrame(frame, GetParam().notes);
    }
  }

  void TearDown() override {
    // Owned web contentses must be destroyed before the test harness. Before
    // doing that, however, clear the instance map of all `UserNoteManager`
    // objects to avoid clean-up issues where the managers attempt to remove
    // themselves from the `UserNoteService`, which won't work because the test
    // setup does not add the manager refs in the service.
    for (const auto& wc : web_contents_list_) {
      UserNoteManager::GetForPage(wc->GetPrimaryPage())->instance_map_.clear();
    }
    web_contents_list_.clear();
    content::RenderViewHostTestHarness::TearDown();
  }

  void CreateNewNoteAndAddToService(const NoteConfig& note_config) {
    int test_id = note_config.test_id;
    ASSERT_TRUE(test_id_to_token_.find(test_id) == test_id_to_token_.end())
        << "Invalid test case configuration: the same note ID (" << test_id
        << ") is used more than once";

    auto token_id = base::UnguessableToken::Create();
    test_id_to_token_.emplace(test_id, token_id);
    token_to_test_id_.emplace(token_id, test_id);

    // Creation time and minimum version are not important for these tests. For
    // modification time, use the default timestamp so that tests with modified
    // notes can use a later timestamp.
    auto note_metadata = std::make_unique<UserNoteMetadata>(
        /*creation_date=*/kInitialTimeStamp,
        /*modification_date=*/kInitialTimeStamp,
        /*min_note_version=*/1);

    auto note = std::make_unique<UserNote>(
        token_id, std::move(note_metadata), GetTestUserNoteBody(),
        GetTestUserNotePageTarget(note_config.target_url));
    UserNoteService::ModelMapEntry entry(std::move(note));
    note_service_->model_map_.emplace(token_id, std::move(entry));
  }

  void ConfigureNewFrame(const FrameConfig& frame_config,
                         const std::vector<NoteConfig>& note_configs) {
    ASSERT_TRUE(config_to_frame_.find(frame_config) == config_to_frame_.end())
        << "Invalid test case configuration: the same frame ID ("
        << frame_config.test_id << ") is used more than once";

    // Create a test frame and navigate it to the specified URL.
    std::unique_ptr<content::WebContents> wc = CreateTestWebContents();
    content::RenderFrameHostTester::For(wc->GetPrimaryMainFrame())
        ->InitializeRenderFrameIfNeeded();
    content::NavigationSimulator::NavigateAndCommitFromBrowser(
        wc.get(), GURL(frame_config.url));

    // Create and attach a `UserNoteManager` to the primary page.
    content::Page& page = wc->GetPrimaryPage();
    UserNoteManager::CreateForPage(page, note_service_->GetSafeRef());
    UserNoteManager* note_manager = UserNoteManager::GetForPage(page);
    DCHECK(note_manager);

    // Attach all notes that have a target URL corresponding to this frame's
    // URL except if their update type is `ADDED`.
    for (const NoteConfig& note_config : note_configs) {
      if (note_config.target_url == frame_config.url &&
          note_config.update_type != NoteUpdateType::ADDED) {
        const auto token_it = test_id_to_token_.find(note_config.test_id);
        DCHECK(token_it != test_id_to_token_.end());

        const auto note_entry_it =
            note_service_->model_map_.find(token_it->second);
        UserNote* model = note_entry_it->second.model.get();
        note_manager->instance_map_.emplace(
            model->id(),
            UserNoteInstance::Create(model->GetSafeRef(), note_manager));
      }
    }

    frame_to_config_.emplace(wc->GetPrimaryMainFrame(), frame_config);
    config_to_frame_.emplace(frame_config, wc->GetPrimaryMainFrame());
    web_contents_list_.emplace_back(std::move(wc));
  }

  void GenerateMetadataUpdateForNote(UserNoteMetadataSnapshot& snapshot,
                                     const NoteConfig& note_config) {
    if (note_config.update_type == NoteUpdateType::REMOVED) {
      // To simulate this note being removed, simply don't include it in the
      // updated metadata snapshot.
      return;
    }

    base::Time modification_date =
        note_config.update_type == NoteUpdateType::MODIFIED ? kUpdatedTimeStamp
                                                            : kInitialTimeStamp;

    // Creation time and minimum version are not important for these tests.
    auto note_metadata = std::make_unique<UserNoteMetadata>(
        /*creation_date=*/kInitialTimeStamp, modification_date,
        /*min_note_version=*/1);

    const auto token_it = test_id_to_token_.find(note_config.test_id);
    DCHECK(token_it != test_id_to_token_.end());

    snapshot.AddEntry(GURL(note_config.target_url), token_it->second,
                      std::move(note_metadata));
  }

  std::unordered_map<base::UnguessableToken, int, base::UnguessableTokenHash>
      token_to_test_id_;
  std::unordered_map<int, base::UnguessableToken> test_id_to_token_;
  std::unordered_map<content::RenderFrameHost*, FrameConfig> frame_to_config_;
  std::unordered_map<FrameConfig, content::RenderFrameHost*, FrameConfigHash>
      config_to_frame_;
  std::vector<std::unique_ptr<content::WebContents>> web_contents_list_;
  std::unique_ptr<UserNoteService> note_service_;
  base::test::ScopedFeatureList scoped_feature_list_;
};

std::vector<UserNoteDiffTestCase> BuildTestCases() {
  std::vector<UserNoteDiffTestCase> test_cases = {
      // Cases without frames and / or notes.
      UserNoteDiffTestCase("no_frames"),

      UserNoteDiffTestCase("multiple_frames_all_without_notes")
          .AddFrame(FrameConfig(0, kUrl1))
          .AddFrame(FrameConfig(1, kUrl2))
          .AddFrame(FrameConfig(2, kUrl3)),

      UserNoteDiffTestCase("multiple_frames_same_url_all_without_notes")
          .AddFrame(FrameConfig(0, kUrl1))
          .AddFrame(FrameConfig(1, kUrl2))
          .AddFrame(FrameConfig(2, kUrl2)),

      // Cases with unchanged notes.
      UserNoteDiffTestCase("one_frame_with_unchanged_notes")
          .AddNote(NoteConfig(0, kUrl1))
          .AddNote(NoteConfig(1, kUrl1))
          .AddFrame(FrameConfig(0, kUrl1)),

      UserNoteDiffTestCase("multiple_frames_some_with_unchanged_notes")
          .AddNote(NoteConfig(0, kUrl1))
          .AddNote(NoteConfig(1, kUrl1))
          .AddFrame(FrameConfig(0, kUrl1))
          .AddFrame(FrameConfig(1, kUrl2))
          .AddFrame(FrameConfig(2, kUrl3)),

      UserNoteDiffTestCase("multiple_frames_all_with_unchanged_notes")
          .AddNote(NoteConfig(0, kUrl1))
          .AddNote(NoteConfig(1, kUrl1))
          .AddNote(NoteConfig(2, kUrl1))
          .AddFrame(FrameConfig(0, kUrl1))
          .AddNote(NoteConfig(3, kUrl2))
          .AddNote(NoteConfig(4, kUrl2))
          .AddNote(NoteConfig(5, kUrl2))
          .AddFrame(FrameConfig(1, kUrl2))
          .AddNote(NoteConfig(6, kUrl3))
          .AddNote(NoteConfig(7, kUrl3))
          .AddNote(NoteConfig(8, kUrl3))
          .AddFrame(FrameConfig(2, kUrl3)),

      UserNoteDiffTestCase("multiple_frames_same_url_all_with_unchanged_notes")
          .AddNote(NoteConfig(0, kUrl1))
          .AddNote(NoteConfig(1, kUrl1))
          .AddNote(NoteConfig(2, kUrl1))
          .AddFrame(FrameConfig(0, kUrl1))
          .AddFrame(FrameConfig(1, kUrl1))
          .AddNote(NoteConfig(3, kUrl2))
          .AddNote(NoteConfig(4, kUrl2))
          .AddNote(NoteConfig(5, kUrl2))
          .AddFrame(FrameConfig(2, kUrl2)),

      // Cases with added notes.
      UserNoteDiffTestCase("one_frame_with_one_added_note")
          .AddNote(NoteConfig(0, kUrl1, NoteUpdateType::ADDED))
          .AddFrame(FrameConfig(0, kUrl1).ExpectAdded({0})),

      UserNoteDiffTestCase("one_frame_with_multiple_added_notes")
          .AddNote(NoteConfig(0, kUrl1, NoteUpdateType::ADDED))
          .AddNote(NoteConfig(1, kUrl1, NoteUpdateType::ADDED))
          .AddFrame(FrameConfig(0, kUrl1).ExpectAdded({0, 1})),

      UserNoteDiffTestCase("multiple_frames_some_with_added_notes")
          .AddNote(NoteConfig(0, kUrl1, NoteUpdateType::ADDED))
          .AddNote(NoteConfig(1, kUrl1, NoteUpdateType::ADDED))
          .AddNote(NoteConfig(2, kUrl1, NoteUpdateType::ADDED))
          .AddFrame(FrameConfig(0, kUrl1).ExpectAdded({0, 1, 2}))
          .AddNote(NoteConfig(3, kUrl2, NoteUpdateType::ADDED))
          .AddNote(NoteConfig(4, kUrl2, NoteUpdateType::ADDED))
          .AddNote(NoteConfig(5, kUrl2, NoteUpdateType::ADDED))
          .AddFrame(FrameConfig(1, kUrl2).ExpectAdded({3, 4, 5}))
          .AddFrame(FrameConfig(2, kUrl3)),

      UserNoteDiffTestCase("multiple_frames_all_with_added_notes")
          .AddNote(NoteConfig(0, kUrl1, NoteUpdateType::ADDED))
          .AddNote(NoteConfig(1, kUrl1, NoteUpdateType::ADDED))
          .AddNote(NoteConfig(2, kUrl1, NoteUpdateType::ADDED))
          .AddFrame(FrameConfig(0, kUrl1).ExpectAdded({0, 1, 2}))
          .AddNote(NoteConfig(3, kUrl2, NoteUpdateType::ADDED))
          .AddNote(NoteConfig(4, kUrl2, NoteUpdateType::ADDED))
          .AddNote(NoteConfig(5, kUrl2, NoteUpdateType::ADDED))
          .AddFrame(FrameConfig(1, kUrl2).ExpectAdded({3, 4, 5}))
          .AddNote(NoteConfig(6, kUrl3, NoteUpdateType::ADDED))
          .AddNote(NoteConfig(7, kUrl3, NoteUpdateType::ADDED))
          .AddNote(NoteConfig(8, kUrl3, NoteUpdateType::ADDED))
          .AddFrame(FrameConfig(2, kUrl3).ExpectAdded({6, 7, 8})),

      UserNoteDiffTestCase("multiple_frames_same_url_all_with_added_notes")
          .AddNote(NoteConfig(0, kUrl1, NoteUpdateType::ADDED))
          .AddNote(NoteConfig(1, kUrl1, NoteUpdateType::ADDED))
          .AddNote(NoteConfig(2, kUrl1, NoteUpdateType::ADDED))
          .AddFrame(FrameConfig(0, kUrl1).ExpectAdded({0, 1, 2}))
          .AddFrame(FrameConfig(1, kUrl1).ExpectAdded({0, 1, 2}))
          .AddNote(NoteConfig(3, kUrl2, NoteUpdateType::ADDED))
          .AddNote(NoteConfig(4, kUrl2, NoteUpdateType::ADDED))
          .AddNote(NoteConfig(5, kUrl2, NoteUpdateType::ADDED))
          .AddFrame(FrameConfig(2, kUrl2).ExpectAdded({3, 4, 5})),

      // Cases with modified notes.
      UserNoteDiffTestCase("one_frame_with_one_modified_note")
          .AddNote(NoteConfig(0, kUrl1, NoteUpdateType::MODIFIED))
          .AddFrame(FrameConfig(0, kUrl1).ExpectModified({0})),

      UserNoteDiffTestCase("one_frame_with_multiple_modified_notes")
          .AddNote(NoteConfig(0, kUrl1, NoteUpdateType::MODIFIED))
          .AddNote(NoteConfig(1, kUrl1, NoteUpdateType::MODIFIED))
          .AddNote(NoteConfig(2, kUrl1, NoteUpdateType::MODIFIED))
          .AddFrame(FrameConfig(0, kUrl1).ExpectModified({0, 1, 2})),

      UserNoteDiffTestCase("multiple_frames_some_with_modified_notes")
          .AddNote(NoteConfig(0, kUrl1, NoteUpdateType::MODIFIED))
          .AddNote(NoteConfig(1, kUrl1, NoteUpdateType::MODIFIED))
          .AddNote(NoteConfig(2, kUrl1, NoteUpdateType::MODIFIED))
          .AddFrame(FrameConfig(0, kUrl1).ExpectModified({0, 1, 2}))
          .AddNote(NoteConfig(3, kUrl2, NoteUpdateType::MODIFIED))
          .AddNote(NoteConfig(4, kUrl2, NoteUpdateType::MODIFIED))
          .AddNote(NoteConfig(5, kUrl2, NoteUpdateType::MODIFIED))
          .AddFrame(FrameConfig(1, kUrl2).ExpectModified({3, 4, 5}))
          .AddFrame(FrameConfig(2, kUrl3)),

      UserNoteDiffTestCase("multiple_frames_all_with_modified_notes")
          .AddNote(NoteConfig(0, kUrl1, NoteUpdateType::MODIFIED))
          .AddNote(NoteConfig(1, kUrl1, NoteUpdateType::MODIFIED))
          .AddNote(NoteConfig(2, kUrl1, NoteUpdateType::MODIFIED))
          .AddFrame(FrameConfig(0, kUrl1).ExpectModified({0, 1, 2}))
          .AddNote(NoteConfig(3, kUrl2, NoteUpdateType::MODIFIED))
          .AddNote(NoteConfig(4, kUrl2, NoteUpdateType::MODIFIED))
          .AddNote(NoteConfig(5, kUrl2, NoteUpdateType::MODIFIED))
          .AddFrame(FrameConfig(1, kUrl2).ExpectModified({3, 4, 5}))
          .AddNote(NoteConfig(6, kUrl3, NoteUpdateType::MODIFIED))
          .AddNote(NoteConfig(7, kUrl3, NoteUpdateType::MODIFIED))
          .AddNote(NoteConfig(8, kUrl3, NoteUpdateType::MODIFIED))
          .AddFrame(FrameConfig(2, kUrl3).ExpectModified({6, 7, 8})),

      UserNoteDiffTestCase("multiple_frames_same_url_all_with_modified_notes")
          .AddNote(NoteConfig(0, kUrl1, NoteUpdateType::MODIFIED))
          .AddNote(NoteConfig(1, kUrl1, NoteUpdateType::MODIFIED))
          .AddNote(NoteConfig(2, kUrl1, NoteUpdateType::MODIFIED))
          .AddFrame(FrameConfig(0, kUrl1).ExpectModified({0, 1, 2}))
          .AddFrame(FrameConfig(1, kUrl1).ExpectModified({0, 1, 2}))
          .AddNote(NoteConfig(3, kUrl2, NoteUpdateType::MODIFIED))
          .AddNote(NoteConfig(4, kUrl2, NoteUpdateType::MODIFIED))
          .AddNote(NoteConfig(5, kUrl2, NoteUpdateType::MODIFIED))
          .AddFrame(FrameConfig(2, kUrl2).ExpectModified({3, 4, 5})),

      // Cases with removed notes.
      UserNoteDiffTestCase("one_frame_one_removed_note")
          .AddNote(NoteConfig(0, kUrl1, NoteUpdateType::REMOVED))
          .AddFrame(FrameConfig(0, kUrl1).ExpectRemoved({0})),

      UserNoteDiffTestCase("one_frame_with_multiple_removed_notes")
          .AddNote(NoteConfig(0, kUrl1, NoteUpdateType::REMOVED))
          .AddNote(NoteConfig(1, kUrl1, NoteUpdateType::REMOVED))
          .AddFrame(FrameConfig(0, kUrl1).ExpectRemoved({0, 1})),

      UserNoteDiffTestCase("multiple_frames_some_with_removed_notes")
          .AddNote(NoteConfig(0, kUrl1, NoteUpdateType::REMOVED))
          .AddNote(NoteConfig(1, kUrl1, NoteUpdateType::REMOVED))
          .AddNote(NoteConfig(2, kUrl1, NoteUpdateType::REMOVED))
          .AddFrame(FrameConfig(0, kUrl1).ExpectRemoved({0, 1, 2}))
          .AddNote(NoteConfig(3, kUrl2, NoteUpdateType::REMOVED))
          .AddNote(NoteConfig(4, kUrl2, NoteUpdateType::REMOVED))
          .AddNote(NoteConfig(5, kUrl2, NoteUpdateType::REMOVED))
          .AddFrame(FrameConfig(1, kUrl2).ExpectRemoved({3, 4, 5}))
          .AddFrame(FrameConfig(2, kUrl3)),

      UserNoteDiffTestCase("multiple_frames_all_with_removed_notes")
          .AddNote(NoteConfig(0, kUrl1, NoteUpdateType::REMOVED))
          .AddNote(NoteConfig(1, kUrl1, NoteUpdateType::REMOVED))
          .AddNote(NoteConfig(2, kUrl1, NoteUpdateType::REMOVED))
          .AddFrame(FrameConfig(0, kUrl1).ExpectRemoved({0, 1, 2}))
          .AddNote(NoteConfig(3, kUrl2, NoteUpdateType::REMOVED))
          .AddNote(NoteConfig(4, kUrl2, NoteUpdateType::REMOVED))
          .AddNote(NoteConfig(5, kUrl2, NoteUpdateType::REMOVED))
          .AddFrame(FrameConfig(1, kUrl2).ExpectRemoved({3, 4, 5}))
          .AddNote(NoteConfig(6, kUrl3, NoteUpdateType::REMOVED))
          .AddNote(NoteConfig(7, kUrl3, NoteUpdateType::REMOVED))
          .AddNote(NoteConfig(8, kUrl3, NoteUpdateType::REMOVED))
          .AddFrame(FrameConfig(2, kUrl3).ExpectRemoved({6, 7, 8})),

      UserNoteDiffTestCase("multiple_frames_same_url_all_with_removed_notes")
          .AddNote(NoteConfig(0, kUrl1, NoteUpdateType::REMOVED))
          .AddNote(NoteConfig(1, kUrl1, NoteUpdateType::REMOVED))
          .AddNote(NoteConfig(2, kUrl1, NoteUpdateType::REMOVED))
          .AddFrame(FrameConfig(0, kUrl1).ExpectRemoved({0, 1, 2}))
          .AddFrame(FrameConfig(1, kUrl1).ExpectRemoved({0, 1, 2}))
          .AddNote(NoteConfig(3, kUrl2, NoteUpdateType::REMOVED))
          .AddNote(NoteConfig(4, kUrl2, NoteUpdateType::REMOVED))
          .AddNote(NoteConfig(5, kUrl2, NoteUpdateType::REMOVED))
          .AddFrame(FrameConfig(2, kUrl2).ExpectRemoved({3, 4, 5})),

      // Cases that mix update types.
      UserNoteDiffTestCase("one_frame_with_one_of_each_update_type")
          .AddNote(NoteConfig(0, kUrl1))
          .AddNote(NoteConfig(1, kUrl1, NoteUpdateType::ADDED))
          .AddNote(NoteConfig(2, kUrl1, NoteUpdateType::MODIFIED))
          .AddNote(NoteConfig(3, kUrl1, NoteUpdateType::REMOVED))
          .AddFrame(FrameConfig(0, kUrl1)
                        .ExpectAdded({1})
                        .ExpectModified({2})
                        .ExpectRemoved({3})),

      UserNoteDiffTestCase("one_frame_with_multiple_of_each_update_type")
          .AddNote(NoteConfig(0, kUrl1))
          .AddNote(NoteConfig(1, kUrl1))
          .AddNote(NoteConfig(2, kUrl1, NoteUpdateType::ADDED))
          .AddNote(NoteConfig(3, kUrl1, NoteUpdateType::ADDED))
          .AddNote(NoteConfig(4, kUrl1, NoteUpdateType::MODIFIED))
          .AddNote(NoteConfig(5, kUrl1, NoteUpdateType::MODIFIED))
          .AddNote(NoteConfig(6, kUrl1, NoteUpdateType::MODIFIED))
          .AddNote(NoteConfig(7, kUrl1, NoteUpdateType::REMOVED))
          .AddNote(NoteConfig(8, kUrl1, NoteUpdateType::REMOVED))
          .AddFrame(FrameConfig(0, kUrl1)
                        .ExpectAdded({2, 3})
                        .ExpectModified({4, 5, 6})
                        .ExpectRemoved({7, 8})),

      UserNoteDiffTestCase("multiple_frames_with_different_update_types")
          .AddNote(NoteConfig(0, kUrl1))
          .AddNote(NoteConfig(1, kUrl1))
          .AddNote(NoteConfig(2, kUrl1, NoteUpdateType::ADDED))
          .AddNote(NoteConfig(3, kUrl1, NoteUpdateType::ADDED))
          .AddFrame(FrameConfig(0, kUrl1).ExpectAdded({2, 3}))
          .AddNote(NoteConfig(4, kUrl2, NoteUpdateType::MODIFIED))
          .AddNote(NoteConfig(5, kUrl2, NoteUpdateType::MODIFIED))
          .AddNote(NoteConfig(6, kUrl2, NoteUpdateType::REMOVED))
          .AddFrame(
              FrameConfig(1, kUrl2).ExpectModified({4, 5}).ExpectRemoved({6}))
          .AddFrame(FrameConfig(2, kUrl3)),

      UserNoteDiffTestCase(
          "multiple_frames_with_multiple_notes_of_each_update_type")
          .AddNote(NoteConfig(0, kUrl1))
          .AddNote(NoteConfig(1, kUrl1))
          .AddNote(NoteConfig(2, kUrl1, NoteUpdateType::ADDED))
          .AddNote(NoteConfig(3, kUrl1, NoteUpdateType::ADDED))
          .AddNote(NoteConfig(4, kUrl1, NoteUpdateType::MODIFIED))
          .AddNote(NoteConfig(5, kUrl1, NoteUpdateType::MODIFIED))
          .AddNote(NoteConfig(6, kUrl1, NoteUpdateType::MODIFIED))
          .AddNote(NoteConfig(7, kUrl1, NoteUpdateType::REMOVED))
          .AddNote(NoteConfig(8, kUrl1, NoteUpdateType::REMOVED))
          .AddFrame(FrameConfig(0, kUrl1)
                        .ExpectAdded({2, 3})
                        .ExpectModified({4, 5, 6})
                        .ExpectRemoved({7, 8}))
          .AddNote(NoteConfig(9, kUrl2))
          .AddNote(NoteConfig(10, kUrl2))
          .AddNote(NoteConfig(11, kUrl2, NoteUpdateType::ADDED))
          .AddNote(NoteConfig(12, kUrl2, NoteUpdateType::ADDED))
          .AddNote(NoteConfig(13, kUrl2, NoteUpdateType::MODIFIED))
          .AddNote(NoteConfig(14, kUrl2, NoteUpdateType::MODIFIED))
          .AddNote(NoteConfig(15, kUrl2, NoteUpdateType::MODIFIED))
          .AddNote(NoteConfig(16, kUrl2, NoteUpdateType::REMOVED))
          .AddNote(NoteConfig(17, kUrl2, NoteUpdateType::REMOVED))
          .AddFrame(FrameConfig(1, kUrl2)
                        .ExpectAdded({11, 12})
                        .ExpectModified({13, 14, 15})
                        .ExpectRemoved({16, 17}))
          .AddNote(NoteConfig(18, kUrl3))
          .AddNote(NoteConfig(19, kUrl3))
          .AddNote(NoteConfig(20, kUrl3, NoteUpdateType::ADDED))
          .AddNote(NoteConfig(21, kUrl3, NoteUpdateType::ADDED))
          .AddNote(NoteConfig(22, kUrl3, NoteUpdateType::MODIFIED))
          .AddNote(NoteConfig(23, kUrl3, NoteUpdateType::MODIFIED))
          .AddNote(NoteConfig(24, kUrl3, NoteUpdateType::MODIFIED))
          .AddNote(NoteConfig(25, kUrl3, NoteUpdateType::REMOVED))
          .AddNote(NoteConfig(26, kUrl3, NoteUpdateType::REMOVED))
          .AddFrame(FrameConfig(2, kUrl3)
                        .ExpectAdded({20, 21})
                        .ExpectModified({22, 23, 24})
                        .ExpectRemoved({25, 26})),

      UserNoteDiffTestCase(
          "multiple_frames_same_url_with_multiple_notes_of_each_update_type")
          .AddNote(NoteConfig(0, kUrl1))
          .AddNote(NoteConfig(1, kUrl1))
          .AddNote(NoteConfig(2, kUrl1, NoteUpdateType::ADDED))
          .AddNote(NoteConfig(3, kUrl1, NoteUpdateType::ADDED))
          .AddNote(NoteConfig(4, kUrl1, NoteUpdateType::MODIFIED))
          .AddNote(NoteConfig(5, kUrl1, NoteUpdateType::MODIFIED))
          .AddNote(NoteConfig(6, kUrl1, NoteUpdateType::MODIFIED))
          .AddNote(NoteConfig(7, kUrl1, NoteUpdateType::REMOVED))
          .AddNote(NoteConfig(8, kUrl1, NoteUpdateType::REMOVED))
          .AddFrame(FrameConfig(0, kUrl1)
                        .ExpectAdded({2, 3})
                        .ExpectModified({4, 5, 6})
                        .ExpectRemoved({7, 8}))
          .AddFrame(FrameConfig(1, kUrl1)
                        .ExpectAdded({2, 3})
                        .ExpectModified({4, 5, 6})
                        .ExpectRemoved({7, 8}))
          .AddNote(NoteConfig(9, kUrl2))
          .AddNote(NoteConfig(10, kUrl2))
          .AddNote(NoteConfig(11, kUrl2, NoteUpdateType::ADDED))
          .AddNote(NoteConfig(12, kUrl2, NoteUpdateType::ADDED))
          .AddNote(NoteConfig(13, kUrl2, NoteUpdateType::MODIFIED))
          .AddNote(NoteConfig(14, kUrl2, NoteUpdateType::MODIFIED))
          .AddNote(NoteConfig(15, kUrl2, NoteUpdateType::MODIFIED))
          .AddNote(NoteConfig(16, kUrl2, NoteUpdateType::REMOVED))
          .AddNote(NoteConfig(17, kUrl2, NoteUpdateType::REMOVED))
          .AddFrame(FrameConfig(2, kUrl2)
                        .ExpectAdded({11, 12})
                        .ExpectModified({13, 14, 15})
                        .ExpectRemoved({16, 17})),

      UserNoteDiffTestCase("multiple_frames_each_with_different_update_types")
          .AddNote(NoteConfig(0, kUrl1))
          .AddNote(NoteConfig(1, kUrl1))
          .AddFrame(FrameConfig(0, kUrl1))
          .AddNote(NoteConfig(2, kUrl2, NoteUpdateType::ADDED))
          .AddNote(NoteConfig(3, kUrl2, NoteUpdateType::ADDED))
          .AddFrame(FrameConfig(1, kUrl2).ExpectAdded({2, 3}))
          .AddNote(NoteConfig(4, kUrl3, NoteUpdateType::MODIFIED))
          .AddNote(NoteConfig(5, kUrl3, NoteUpdateType::MODIFIED))
          .AddNote(NoteConfig(6, kUrl3, NoteUpdateType::MODIFIED))
          .AddFrame(FrameConfig(2, kUrl3).ExpectModified({4, 5, 6}))
          .AddNote(NoteConfig(7, kUrl4, NoteUpdateType::REMOVED))
          .AddNote(NoteConfig(8, kUrl4, NoteUpdateType::REMOVED))
          .AddFrame(FrameConfig(3, kUrl4).ExpectRemoved({7, 8}))
          .AddFrame(FrameConfig(4, kUrl5))};

  return test_cases;
}

INSTANTIATE_TEST_SUITE_P(/* No prefix */,
                         UserNoteUtilsTest,
                         testing::ValuesIn(BuildTestCases()),
                         DescribeParams);

TEST_P(UserNoteUtilsTest, CalculateNoteChanges) {
  // Construct the metadata snapshot from the note configs as if there had been
  // an update sent by the database.
  UserNoteMetadataSnapshot metadata_snapshot;
  for (const NoteConfig& note_config : GetParam().notes) {
    GenerateMetadataUpdateForNote(metadata_snapshot, note_config);
  }

  // Round up the test frames as if they were the user's open tabs.
  std::vector<content::WeakDocumentPtr> weak_documents;
  weak_documents.reserve(frame_to_config_.size());
  for (const auto& config_it : frame_to_config_) {
    weak_documents.emplace_back(config_it.first->GetWeakDocumentPtr());
  }

  // Calculate the diff between the notes in the frames and the notes in the
  // metadata.
  const std::vector<std::unique_ptr<FrameUserNoteChanges>>& actual_diffs =
      CalculateNoteChanges(*note_service_, weak_documents, metadata_snapshot);

  std::unordered_set<content::RenderFrameHost*> frames_with_diff;
  for (const std::unique_ptr<FrameUserNoteChanges>& diff : actual_diffs) {
    content::RenderFrameHost* rfh = diff->document_.AsRenderFrameHostIfValid();
    // Find the frame config for this diff's frame.
    const auto config_it = frame_to_config_.find(rfh);
    DCHECK(config_it != frame_to_config_.end());
    FrameConfig frame_config = config_it->second;

    // Make sure there is at most one diff per frame.
    EXPECT_TRUE(frames_with_diff.find(rfh) == frames_with_diff.end())
        << "More than one diff generated for frame " << frame_config.test_id;
    frames_with_diff.emplace(rfh);

    // Verify that a diff was expected for this frame.
    EXPECT_TRUE(frame_config.expect_diff)
        << "A diff was unexpectedly generated for frame "
        << frame_config.test_id;

    // Verify added, modified and removed notes are as expected. Use copies to
    // prevent any side effect of sorting in place.
    NoteIdList actual_added =
        ConvertToSortedTestIds(diff->notes_added_, token_to_test_id_);
    NoteIdList expected_added = CopyAndSort(frame_config.added);
    EXPECT_EQ(actual_added, expected_added)
        << "Unexpected ADDED results for frame " << frame_config.test_id;

    NoteIdList actual_modified =
        ConvertToSortedTestIds(diff->notes_modified_, token_to_test_id_);
    NoteIdList expected_modified = CopyAndSort(frame_config.modified);
    EXPECT_EQ(actual_modified, expected_modified)
        << "Unexpected MODIFIED results for frame " << frame_config.test_id;

    NoteIdList actual_removed =
        ConvertToSortedTestIds(diff->notes_removed_, token_to_test_id_);
    NoteIdList expected_removed = CopyAndSort(frame_config.removed);
    EXPECT_EQ(actual_removed, expected_removed)
        << "Unexpected REMOVED results for frame " << frame_config.test_id;
  }

  // Make sure there are no missing diffs.
  for (const auto& frame_it : config_to_frame_) {
    if (frame_it.first.expect_diff) {
      EXPECT_FALSE(frames_with_diff.find(frame_it.second) ==
                   frames_with_diff.end())
          << "A diff was unexpectedly missing for frame "
          << frame_it.first.test_id;
    }
  }
}

}  // namespace user_notes
